home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1997 / MacHack 1997.toast / Hacks / Hacks ’97 / Warrior’s Progress / source code / Source / Libraries / Trees / RedBlackTree.cp < prev    next >
Encoding:
Text File  |  1997-06-28  |  4.5 KB  |  231 lines  |  [TEXT/CWIE]
  1. // RedBlackTree.cp
  2.  
  3. #ifndef RedBlackTree_h
  4. #include "RedBlackTree.h"
  5. #endif
  6. #ifndef RedBlackNode_h
  7. #include "RedBlackNode.h"
  8. #endif
  9.  
  10. RedBlackTree::RedBlackTree()
  11.   : blackHeight( 0 )
  12.   {
  13.   }
  14.  
  15. RedBlackTree::~RedBlackTree()
  16.   {
  17.     Assert( blackHeight == 0 );
  18.   }
  19.  
  20. RedBlackNode *RedBlackTree::DownCast( TreeNode *n )
  21.   {
  22.     return static_cast< RedBlackNode* >( n );
  23.   }
  24.  
  25. const RedBlackNode *RedBlackTree::DownCast( const TreeNode *n )
  26.   {
  27.     return static_cast< const RedBlackNode* >( n );
  28.   }
  29.  
  30. void RedBlackTree::Add( RedBlackNode& newNode, AtRoot )
  31.   {
  32.     Assert( newNode.IsRed() );
  33.     Tree::Add( newNode, atRoot );
  34.     Assert( blackHeight == 0 );
  35.   }
  36.  
  37. void RedBlackTree::Add( RedBlackNode& newNode,
  38.                                 Before,
  39.                                 RedBlackNode& next )
  40.   {
  41.     Assert( newNode.IsRed() );
  42.     Assert( !next.HasLeftChild() );
  43.     Assert( next.IsBlack() || !next.HasRightChild() );
  44.     Assert( !next.HasRightChild() || next.Right()->IsRed() );
  45.     Assert( !next.HasRightChild() || next.Right()->IsLeaf() );
  46.     
  47.     Tree::Add( newNode, before, next );
  48.     FixRedChain( newNode );
  49.   }
  50.  
  51. void RedBlackTree::Add( RedBlackNode& newNode,
  52.                                 After,
  53.                                 RedBlackNode& previous )
  54.   {
  55.     Assert( newNode.IsRed() );
  56.     Assert( !previous.HasRightChild() );
  57.     Assert( previous.IsBlack() || previous.IsLeaf() );
  58.     Assert( !previous.HasLeftChild() || previous.Left()->IsRed() );
  59.     Assert( !previous.HasLeftChild() || previous.Left()->IsLeaf() );
  60.  
  61.     Tree::Add( newNode, after, previous );
  62.     FixRedChain( newNode );
  63.   }
  64.  
  65. void RedBlackTree::Remove( RedBlackNode& toRemove )
  66.   {
  67.     if ( toRemove.HasLeftChild() )
  68.       {
  69.         RedBlackNode *previous = toRemove.Previous();
  70.         Assert( previous != 0 );
  71.         toRemove.SwapWith( *previous );
  72.     
  73.         if ( toRemove.HasLeftChild() )
  74.           {
  75.             Assert( toRemove.Left()->IsRed() );
  76.             toRemove.Left()->RotateUp();
  77.           }
  78.       }
  79.      else if ( toRemove.HasRightChild() )
  80.       {
  81.         RedBlackNode *next = toRemove.Next();
  82.         Assert( next != 0 );
  83.         toRemove.SwapWith( *next );
  84.     
  85.         if ( toRemove.HasRightChild() )
  86.           {
  87.             Assert( toRemove.Right()->IsRed() );
  88.             toRemove.Right()->RotateUp();
  89.           }
  90.       }
  91.  
  92.     Assert( toRemove.IsLeaf() );
  93.     Redden( toRemove );
  94.     Tree::Remove( toRemove );
  95.   }
  96.  
  97. void RedBlackTree::RemoveAll()
  98.   {
  99.     RedBlackNode *first = First();
  100.     while ( first != 0 )
  101.       {
  102.         Assert( !first->HasLeftChild() );
  103.         
  104.         if ( first->HasRightChild() )
  105.             Remove( *first->Right() );
  106.         
  107.         Assert( !first->HasRightChild() );
  108.         
  109.         RedBlackNode *next = first->Parent();
  110.         Remove( *first );
  111.         first = next;
  112.       }
  113.   }
  114.  
  115. void RedBlackTree::FixRedChain( RedBlackNode& toFix )
  116.   {
  117.     Assert( &toFix.Owner() == this );
  118.     
  119.     RedBlackNode *lower = &toFix;
  120.     
  121.     while ( true )
  122.       {
  123.         Assert( lower != 0 );
  124.         Assert( lower->IsRed() );
  125.         
  126.         RedBlackNode *upper = lower->Parent();
  127.         
  128.         if ( upper == 0 || upper->IsBlack() )
  129.             break;
  130.         
  131.         if ( upper->IsRoot() )
  132.           {
  133.             upper->red = false;
  134.             blackHeight++;
  135.             break;
  136.           }
  137.     
  138.         RedBlackNode *sibling = upper->Sibling();
  139.         
  140.         if ( sibling == 0 || sibling->IsBlack() )
  141.           {
  142.             if ( lower->IsLeftChild() != upper->IsLeftChild() )
  143.               {
  144.                 lower->RotateUp();
  145.                 lower->RotateUp();
  146.               }
  147.              else
  148.                 upper->RotateUp();
  149.             break;
  150.           }
  151.     
  152.         lower = upper->Parent();
  153.         lower->Raise();
  154.       }
  155.   }
  156.  
  157. void RedBlackTree::Redden( RedBlackNode& toRedden )
  158.   {
  159.     Assert( &toRedden.Owner() == this );
  160.     Assert( toRedden.RedChildren() == 0 );
  161.     
  162.     if ( toRedden.IsRed() )
  163.         return;
  164.     
  165.     // Try changing the root color
  166.       {
  167.         if ( toRedden.IsRoot() )
  168.           {
  169.             Assert( blackHeight > 0 );
  170.             toRedden.red = true;
  171.             blackHeight--;
  172.             return;
  173.           }
  174.       }
  175.     
  176.     RedBlackNode *sibling = toRedden.Sibling();
  177.     Assert( sibling != 0 );
  178.     if ( sibling->IsRed() )
  179.       {
  180.         sibling->RotateUp();
  181.         sibling = toRedden.Sibling();
  182.         Assert( sibling != 0 );
  183.       }
  184.     Assert( !sibling->IsRed() );
  185.     
  186.     // If we have a red left niece, borrow from our sibling
  187.       {
  188.         RedBlackNode *leftNiece = sibling->Left();
  189.         if ( leftNiece != 0 && leftNiece->IsRed() )
  190.           {
  191.             if ( sibling->IsLeftChild() )
  192.                 sibling->RotateUp();
  193.              else
  194.               {
  195.                 leftNiece->RotateUp();
  196.                 leftNiece->RotateUp();
  197.               }
  198.             Assert( toRedden.IsRed() );
  199.             return;
  200.           }
  201.       }
  202.     
  203.     // If we have a red right niece, borrow from our sibling
  204.       {
  205.         RedBlackNode *rightNiece = sibling->Right();
  206.         if ( rightNiece != 0 && rightNiece->IsRed() )
  207.           {
  208.             if ( sibling->IsRightChild() )
  209.                 sibling->RotateUp();
  210.              else
  211.               {
  212.                 rightNiece->RotateUp();
  213.                 rightNiece->RotateUp();
  214.               }
  215.             Assert( toRedden.IsRed() );
  216.             return;
  217.           }
  218.       }
  219.     
  220.     Redden( *toRedden.Parent() );
  221.     toRedden.Parent()->Lower();
  222.   }
  223.  
  224. bool RedBlackTree::Valid() const
  225.   {
  226.     if ( IsEmpty() )
  227.         return blackHeight == 0;
  228.     
  229.     return Root()->Valid( blackHeight );
  230.   }
  231.